package com.datastructures2.test;

import com.datastructures2.背包队列栈.Queue;

/**
 * N个键的有序数组最多需要N+1次比较
 * @author MaoLin Wang
 * @date 2020/3/118:43
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> {
   private Key[]keys;
   private Value[]values;
   private int size;

    public BinarySearchST(int size) {
        this.size = size;
        this.keys= (Key[]) new Comparable[size];
        values= (Value[]) new Comparable[size];
    }

    public int size(){return size;}

    public boolean isEmpty(){
        return size==0;
    }
    public Value get(Key key){
        if (key==null)return null;
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            return values[i];
        }else {
            return null;
        }
    }

    public void put(Key key,Value value){
        if (key==null){
            return;
        }
        if (value==null){
            delete(key);
        }
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            values[i]=value;
        }else {
            for (int j = size; j >i ; j--) {
                keys[j]=keys[j-1];
                values[j]=values[j-1];
            }
            keys[i]=key;
            values[i]=value;
            size++;
        }
    }

    private void delete(Key key) {
        if (key==null){
            return;
        }
        int i=rank(key);
        Key delKey=keys[i];
        if (i<size&&keys[i].compareTo(key)==0){
            for (int j=i;j<size-1;j++){
                keys[j]=keys[j+1];
                values[j]=values[j+1];
            }
            keys[--size]=null;
            values[size]=null;
            return;
        }

    }

    private int rank(Key key) {
       int left=0,right=size-1;
       while (left<=right){
           int mid=(left+right)/2;
           int result=key.compareTo(keys[mid]);
           if (result<0){
               right=mid-1;
           }else if (result>0){
               left=mid+1;
           }else {
               return mid;
           }
       }
       return left;
    }

    public static void main(String[] args) {
        BinarySearchST<String,Integer>binarySearchST=new BinarySearchST<>(5);
        binarySearchST.put("a",3);
        binarySearchST.put("d",2);
        binarySearchST.put("c",1);
        binarySearchST.put("b",0);
        binarySearchST.put("e",4);
        System.out.println(binarySearchST.size);
        binarySearchST.delete("b");
        System.out.println(binarySearchST.size);
    }
}
